package com.ting.test.algorithms.大厂刷题班;

/**
 * 给定一个子数组
 * 只能对Arr中的一个子数组排序
 * 但是想让Arr整体有序
 * 返回满足这一要求的最短子数组的长度
 */
public class 需要排序的最短子数组长度 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 6, 5, 7, 4, 8, 9};

        int length = process(arr);
    }

    private static int process(int[] arr) {
        if (arr == null) {
            return 0;
        }

        int L = 0;
        int Max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (Max < arr[i]) {
                Max = arr[i];//如果当前数比Max大，则更新Max
            } else {
                L = i;//记录i位置
            }
        }

        int R = arr.length - 1;
        int Min = arr[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] < Min) {
                Min = arr[i];
            } else {
                R = i;
            }
        }
        return R - L + 1;
    }
}
